﻿
using lib;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MergeTwoLists
{
    class Program
    {
        static void Main(string[] args)
        {
            var head = new ListNode(1);
            head.next = new ListNode(2);
            head.next.next = new ListNode(3);
            head.next.next.next = new ListNode(4);
            head.next.next.next.next = new ListNode(5);

            var head1 = new ListNode(2);
            head1.next = new ListNode(3);
            head1.next.next = new ListNode(7);

            ListNode.Print(MergeTwoLists(head, head1));
            Console.ReadKey();
        }
        public static ListNode MergeTwoLists1(ListNode l1, ListNode l2)
        {
            if (l1 == null || l2 == null)
            {
                if (l1 == null && l2 == null)
                {
                    return null;
                }
                else
                {
                    return l1 == null ? l2 : l1;
                }
            }
            ListNode result = null;
            if (l1.val < l2.val)
            {
                result = l1;
                result.next = MergeTwoLists(l1.next, l2);
            }
            else
            {
                result = l2;
                result.next = MergeTwoLists(l1, l2.next);
            }
            return result;
        }
        public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            

            ListNode newListNode = new ListNode(0);
            ListNode listNode = newListNode;
            var currentNode = l1;
            while (l1 != null&&l2!=null)
            {
                if (l1.val <= l2.val)
                {
                    newListNode.next = l1;
                    l1 = l1.next;
                }
                else
                {
                    newListNode.next = l2;
                    l2 = l2.next;
                }
                newListNode = newListNode.next;
            }
            while (l1 != null)
            {
                newListNode.next = l1;
                l1 = l1.next;
                newListNode = newListNode.next;
            }
            while (l2 != null)
            {
                newListNode.next = l2;
                l2 = l2.next;
                newListNode = newListNode.next;
            }
            return listNode.next;
        }
    }
}
